# 超时
# class Solution(object):
#     def lenLongestFibSubseq(self, arr):
#         n = len(arr)
#         max_len = 0
#         for i in range(n):
#             for j in range(i + 1, n):
#                 count = 2
#                 num1 = arr[i]
#                 num2 = arr[j]
#                 k = j + 1
#                 while k < n and arr[k] <= num1 + num2:
#                     if arr[k] < num1 + num2:
#                         k += 1
#                     else:
#                         num1 = num2
#                         num2 = arr[k]
#                         count += 1
#                         k += 1
#                 if count >= 3:
#                     max_len = max(max_len, count)
#         return max_len
import collections
class Solution(object):
    def lenLongestFibSubseq(self, arr):
        n = len(arr)
        DP = [collections.defaultdict(int) for _ in range(n)]
        DP[1][arr[0]] = 1
        max_len = 0
        for i in range(2, n):
            for j in range(i):
                DP[i][arr[j]] = DP[j][arr[i] - arr[j]] + 1
                max_len = max(max_len, DP[i][arr[j]] + 1)
        if max_len >= 3:
            return max_len
        else:
            return 0


data = Solution()
arr = [1, 2, 3, 4, 5, 6, 7, 8]
print(data.lenLongestFibSubseq(arr))
arr = [1, 3, 7, 11, 12, 14, 18]
print(data.lenLongestFibSubseq(arr))
